package com.example.mydemo

import org.junit.Test
import java.lang.Integer.max
import java.util.PriorityQueue
import java.util.Stack

/*
 * CreateBy:Joker
 * CreateTime:2023/11/9 15:35
 * description：
 */
class ZiJieLiKouTest {

    class ListNode(var data: Int) {
        var next: ListNode? = null //对象：引用下一个节点对象。在Java中没有指针的概念，Java中的引用和C语言的指针类似。
    }


    /*
     *  https://leetcode.cn/problems/decode-the-message/description/
     * 解密消息
     */
    @Test
    fun test1() {
        val key = "the quick brown fox jumps over the lazy dog"
        val message = "vkbs bs t suepuv"
        println(decodeMessage(key, message))

        val map = CharArray(26)
        println(map['t' - 'a'].code)
        map['t' - 'a'] = 'a' + 1
        println(map['t' - 'a'])
    }

    private fun decodeMessage(key: String, message: String): String {
        val map = CharArray(26)
        var index = 0
        for (ch in key) {
            if (!ch.isLetter()) continue

            if (map[ch - 'a'].code == 0) {
                map[ch - 'a'] = 'a' + index
                index++
            }
        }

        return message.map { if (it.isLetter()) map[it - 'a'] else it }.joinToString("")
    }

    /*
     * https://leetcode.cn/problems/two-sum/description/
     * 两数之和
     */
    @Test
    fun test2() {
        val thirdNumbers = intArrayOf(3, 7, 1, 2, 3, 4, 5, 6)
        val thirdTarget = 6
        println(hashTwoSum(thirdNumbers, thirdTarget).contentToString())
    }

    private fun hashTwoSum(numbers: IntArray, target: Int): IntArray {
        hashMapOf<Int, Int>().apply {
            numbers.forEachIndexed { index, number ->
                val other = target - number
                if (containsKey(other)) {
                    val otherIndex = get(other) ?: 0
                    return intArrayOf(otherIndex, index)
                }
                put(number, index)
            }
        }
        return intArrayOf()
    }

    /*
     * https://leetcode.cn/problems/add-two-numbers/description/
     * 两数相加
     */
    @Test
    fun test3() {
        addTwoNumbers(ListNode(4), ListNode(5))
    }

    private fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        return dfs(l1, l2, 0)
    }

    private fun dfs(l: ListNode?, r: ListNode?, i: Int): ListNode? {
        if (l == null && r == null && i == 0) return null
        val sum: Int = (l?.data ?: 0) + (r?.data ?: 0) + i
        val node = ListNode(sum % 10)
        node.next = dfs(l?.next, r?.next, sum / 10)
        return node
    }


    /*
     * https://leetcode.cn/problems/longest-palindromic-substring/description/
     * 最长回文子串
     */
    @Test
    fun test4() {
        println(longestPalindrome("babad"))
        println(longestPalindrome("aaabbbbccccddd"))
    }

    private fun longestPalindrome(s1: String): String {
        val n = s1.length
        val dp = Array(n) { BooleanArray(n) }
        var ml = 0
        var mr = 0
        for (j in 1 until n) {
            for (i in 0 until j) {
                dp[i][j] = s1[i] == s1[j] && (j - i <= 2 || dp[i + 1][j - 1])
                if (dp[i][j] && mr - ml < j - i) {
                    mr = j
                    ml = i
                }
            }
        }
        return s1.substring(ml, mr + 1)
    }

    /*
     * https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
     * 寻找两个正序数组的中位数
     */
    @Test
    fun test5() {
        println(findMedianSortedArrays(intArrayOf(1, 3), intArrayOf(2)))
        println(findMedianSortedArrays(intArrayOf(1, 3), intArrayOf(2, 4)))
        println(findMedianSortedArrays(intArrayOf(), intArrayOf(2)))
        println(findMedianSortedArrays(intArrayOf(0), intArrayOf(2)))

        println(findMedianSortedArrays2(mutableListOf(1, 3), mutableListOf(2)))
        println(findMedianSortedArrays2(mutableListOf(1, 3), mutableListOf(2, 4)))
        println(findMedianSortedArrays2(mutableListOf(), mutableListOf(2)))
        println(findMedianSortedArrays2(mutableListOf(0), mutableListOf(2)))
    }

    private fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val size1 = nums1.size
        val size2 = nums2.size
        // 合并后的数组的索引
        var index = 0
        // 第一个数组的指针，下面用i指针描述
        var i = 0
        // 第二个数组的指针，下面用j指针描述
        var j = 0
        // 合并两个数组
        // 创建一个大小是两个数组长度之和的数组
        val arrays = IntArray(size1 + size2)
        while (i < size1 || j < size2) {
            when {
                // 如果第一个数组遍历完毕后，就继续遍历第二个数组
                i == size1 -> arrays[index++] = nums2[j++]
                // 如果第二个数组遍历完毕后，就继续遍历第一个数组
                j == size2 -> arrays[index++] = nums1[i++]
                // 如果第一个数组的元素小于第二个数组的元素，就将第一个数组中的该元素添加到合并后的新数组，同时将i指针向右移动一格
                nums1[i] < nums2[j] -> arrays[index++] = nums1[i++]
                // 如果第一个数组的元素大于第二个数组的元素，就将第二个数组中的该元素添加到合并后的新数组，同时将j指针向右移动一格
                else -> arrays[index++] = nums2[j++]
            }
        }
        // 找出数组的中位数
        val size = arrays.size
        return if (size % 2.0 == 0.0) {
            // 如果数组长度是偶数，就找出这条中线旁边的两个元素，然后相加之后除以2得到结果
            (arrays[size / 2] + arrays[size / 2 - 1]) / 2.0
        } else {
            // 如果数组长度是奇数，就找出这条中线对应的元素，该元素就是结果
            arrays[size / 2].toDouble()
        }
    }

    private fun findMedianSortedArrays2(nums1: MutableList<Int>, nums2: MutableList<Int>): Double {

        val arrays = nums1 + nums2
        val sortArrays = arrays.sorted()

        // 找出数组的中位数
        val size = sortArrays.size
        return if (size % 2.0 == 0.0) {
            // 如果数组长度是偶数，就找出这条中线旁边的两个元素，然后相加之后除以2得到结果
            (sortArrays[size / 2] + sortArrays[size / 2 - 1]) / 2.0
        } else {
            // 如果数组长度是奇数，就找出这条中线对应的元素，该元素就是结果
            sortArrays[size / 2].toDouble()
        }
    }

    /*
     * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
     * 无重复字符的最长子串
     */
    @Test
    fun test6() {
        println(lengthOfLongestSubstring("abcdefgalaskdjf;asldkfja;slkf"))
    }

    private fun lengthOfLongestSubstring(s1: String): Int {
        val last = Array(128) { _ -> -1 }
        var left = -1
        var ans = 0
        for (i in s1.indices) {
            val si = s1[i].code
            left = max(left, last[si])
            last[si] = i
            ans = max(ans, i - left)
        }
        return ans
    }

    /*
     * https://leetcode.cn/problems/binary-search/description/
     * 二分查找
     */
    @Test
    fun test7() {
        println(search(intArrayOf(-1, 0, 3, 5, 9, 12), 9))
        println(search(intArrayOf(-1, 0, 3, 5, 9, 12), 3))

        var a = 1
        a = 5 / 2
        val b = 5 % 2
        println(a)
        println(b)
    }

    private fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            when {
                nums[mid] == target -> return mid
                nums[mid] < target -> left = mid + 1
                nums[mid] > target -> right = mid - 1
            }
        }
        return -1
    }

    /*
     * https://leetcode.cn/problems/valid-parentheses/description/
     * 有效的括号
     */
    @Test
    fun test8() {
        println(isValid("()[]{}"))
        println(isValid("()[]{"))
        println(isValid("{()[]}"))
    }

    private fun isValid(s: String): Boolean {
        var s1 = s

        if (s1.length % 2 != 0) return false

        while (s1.contains("()") || s1.contains("[]") || s1.contains("{}")) {
            s1 = s1.replace("()", "").replace("[]", "").replace("{}", "")
        }
        return s1.isEmpty()

    }

    /*
     * https://leetcode.cn/problems/longest-common-prefix/description/
     * 最长公共前缀
     */
    @Test
    fun test9() {
        println(longestCommonPrefix(mutableListOf("flower", "flow", "flight", "fl1afl")))
    }

    private fun longestCommonPrefix(strs: MutableList<String>): String {
        if (strs.isEmpty()) return ""
        strs.sort()
        val st = strs[0]
        val end = strs[strs.size - 1]
        var i = 0
        val num = minOf(st.length, end.length)
        while (i < num && st[i] == end[i]) {
            i++
        }
        return st.substring(0, i)
    }


    /*
     * https://leetcode.cn/problems/trapping-rain-water/description/
     * 接雨水
     */
    @Test
    fun test10() {
        println(trap(intArrayOf(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))
    }

    private fun trap(height: IntArray): Int {
        val n = height.size
        var left = 0
        var right = n - 1
        var leftMax = 0
        var rightMax = 0
        var answer = 0
        while (left < right) {
            leftMax = Math.max(leftMax, height[left])
            rightMax = Math.max(rightMax, height[right])
            if (leftMax < rightMax) {
                answer += leftMax - height[left]
                left++
            } else {
                answer += rightMax - height[right]
                right--
            }
        }

        return answer
    }

    /*
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
     * 买卖股票的最佳时机
     */
    @Test
    fun test11() {
        println(maxProfit(intArrayOf(7, 1, 5, 3, 6, 4)))
    }

    private fun maxProfit(prices: IntArray): Int {
        var minprice = Int.MAX_VALUE
        var maxprofit = 0
        for (price in prices) {
            when {
                price < minprice -> minprice = price
                price - minprice > maxprofit -> maxprofit = price - minprice
            }
            println("$minprice / $maxprofit")
        }
        return maxprofit
    }

    /*
    * https://leetcode.cn/problems/3sum/description/
    * 三数之和
    */
    @Test
    fun test12() {
        println(threeSum(intArrayOf(-1, 0, 1, 2, -1, -4)))
    }

    private fun threeSum(nums: IntArray): List<List<Int>> {
        val end = nums.size
        nums.sort()
        println(nums.contentToString())

        val res = mutableListOf<List<Int>>()

        //全是负数过滤
        if (nums[0] > 0 || nums[end - 1] < 0) return res

        for (i in 0 until end - 2) {
            //排序过，第一个为正数，过滤
            if (nums[i] > 0) break

            if (i > 0 && nums[i] == nums[i - 1]) continue

            // twoSum for -nums[i], in range [i+1, n-1]
            var left = i + 1
            var right = end - 1
            while (left < right) {

                val ts = nums[left] + nums[right]

                when {
                    ts == -nums[i] -> {
                        res.add(listOf(nums[i], nums[left], nums[right]))
                        left++
                        while (left < end && nums[left] == nums[left - 1]) {
                            left++
                        }
                    }

                    ts > -nums[i] -> right--

                    else -> left++
                }
            }
        }
        return res
    }


    /*
    * https://leetcode.cn/problems/generate-parentheses/description/
    * 括号生成
    */
    @Test
    fun test13() {
        println(generateParenthesis(3))
    }

    private fun generateParenthesis(n: Int): List<String> {
        val res = mutableListOf<String>()
        if (n == 0) return res

        // ((()))
        // 添加 ( , 左括号只要小于 n，left 随时可以加
        // 添加 ) ，右括号之前必须有左括号，左括号个数 > 右括号个数
        generate(0, 0, n, StringBuilder(), res)

        return res
    }

    private fun generate(left: Int, right: Int, n: Int, str: StringBuilder, res: MutableList<String>) {
        // 若左括号比n多 或者 左括号比右括号少，说明不合法，即"剪枝"
        if (left > n || left < right) return

        // 当所有括号都用完时，得到一个合法的括号组合
        if (left == n && right == n) {
            res.add(str.toString())
            return
        }

        // 尝试添加一个左括号
        str.append("(")                               // 选择
        generate(left + 1, right, n, str, res)
        str.deleteCharAt(str.length - 1)       // 撤消选择

        // 尝试添加一个右括号
        str.append(")")
        generate(left, right + 1, n, str, res)
        str.deleteCharAt(str.length - 1)
    }


    /*
     * https://leetcode.cn/problems/edit-distance/description/
     * 编辑距离
     */
    @Test
    fun test14() {
        println(minDistance("horse", "ros"))
    }

    private fun minDistance(s1: String, s2: String): Int {
        val m = s1.length + 1
        val n = s2.length + 1

        val dp = Array(m) { IntArray(n) }

        // base case
        for (i in 0 until m) dp[i][0] = i
        for (j in 0 until n) dp[0][j] = j

        // dp
        for (i in 1 until m) {
            for (j in 1 until n) {
                when {
                    s1[i - 1] == s2[j - 1] -> {
                        // s1[i]和s2[j] 跳过 ，啥都不做
                        dp[i][j] = dp[i - 1][j - 1]
                    }

                    else -> {
                        dp[i][j] = myMin(
                            // s1中插入一个和s2[j]一样的字符，s2[j]就被匹配了，前移j，继续跟i对比。操作数+1
                            dp[i][j - 1] + 1,
                            // 把s1[i]这个字符删掉，前移i，继续跟j对比。操作数+1
                            dp[i - 1][j] + 1,
                            // 把s1[i]替换成s2[j]，它俩就匹配了，同时前移i，j，继续对比。操作数+1
                            dp[i - 1][j - 1] + 1
                        )
                    }
                }
            }
        }

        // 返回 s1[0..m-1] 和 s2[0..n-1] 的最小编辑距离
        return dp[m - 1][n - 1]
    }

    private fun myMin(a: Int, b: Int, c: Int): Int {
        return Math.min(a, Math.min(b, c))
    }


    /*
    * https://leetcode.cn/problems/merge-two-sorted-lists/description/
    * 合并两个有序链表
    */
    @Test
    fun test15() {
        val l1 = ListNode(1)
        l1.next = ListNode(2)
        l1.next?.next = ListNode(4)

        val l2 = ListNode(1)
        l2.next = ListNode(3)
        l2.next?.next = ListNode(4)

        val l3 = mergeTwoLists(l1, l2)
        println()
    }

    private fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        //递归
        return when {
            l1 == null -> l2
            l2 == null -> l1
            l1.data < l2.data -> {
                l1.next = mergeTwoLists(l1.next, l2)
                l1
            }

            else -> {
                l2.next = mergeTwoLists(l1, l2.next)
                l2
            }
        }
    }


    /*
     * https://leetcode.cn/problems/number-of-islands/description/
     * 岛屿数量
     */
    @Test
    fun test16() {

    }

    private fun numIslands(grid: Array<CharArray>): Int {
        var count = 0
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j)
                    count++
                }
            }
        }
        return count
    }

    private fun dfs(grid: Array<CharArray>, i: Int, j: Int) {
        if (i >= 0 && i < grid.size && j >= 0 && j < grid[0].size && grid[i][j] == '1') {
            grid[i][j] = '0'
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
        }
    }

    /*
     * https://leetcode.cn/problems/maximum-subarray/description/
     * 最大子数组和
     */
    @Test
    fun test17() {
        println(maxSubArray(intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)))
    }

    private fun maxSubArray(nums: IntArray): Int {
        var thisSum = 0
        var maxSum = nums[0]

        for (x in nums) {
            thisSum += x

            if (thisSum > maxSum) {
                maxSum = thisSum
            }

            if (thisSum < 0) {
                thisSum = 0
            }
        }
        return maxSum
    }


    /*
    *  https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
    *  数组中的第K个最大元素
    */
    @Test
    fun test18() {
        println(findKthLargest(intArrayOf(9, 9, 9, 9, 5, 5, 5, 5, 5, 3, 2, 1, 5, 6, 4), 6))
        println(findKthLargest2(intArrayOf(9, 9, 9, 9, 5, 5, 5, 5, 5, 3, 2, 1, 5, 6, 4), 6))

        println(findKthLargest(intArrayOf(9, 9, 9, 9, 5, 5, 5, 5, 5, 3, 2, 1, 5, 6, 4), 8))
        println(findKthLargest2(intArrayOf(9, 9, 9, 9, 5, 5, 5, 5, 5, 3, 2, 1, 5, 6, 4), 8))

    }

    private fun findKthLargest(nums: IntArray, k: Int): Int {
        val heap = PriorityQueue<Int>(nums.size) { t, t2 -> t2 - t }
        nums.forEach { heap.add(it) }
        var count = k

        var res = 0

        while (count > 0) {
            res = heap.poll() ?: 0
            count--
        }

        return res
    }

    private fun findKthLargest2(nums: IntArray, k: Int): Int {
        nums.sortDescending()
        // println(nums.contentToString())
        nums.forEachIndexed { index, i -> if (index == k - 1) return i }

        return 0
    }

    /*
     * https://leetcode.cn/problems/coin-change/description/
     * 零钱兑换
     */
    @Test
    fun test19() {
        println(coinChange(intArrayOf(1, 2, 5), 11))
        println(coinChange(intArrayOf(1, 2, 5), 4))
        println(coinChange(intArrayOf(1, 2, 5), 114))
    }

    private fun coinChange(coins: IntArray, amount: Int): Int {
        val n = amount + 1
        val dp = IntArray(n) { n }
        dp[0] = 0
        for (i in 1 until n) {
            for (c in coins) {
                if (i >= c) {
                    dp[i] = Math.min(dp[i], dp[i - c] + 1)
                }
            }
        }
        return if (dp[amount] > amount) -1 else dp[amount]
    }

    /*
     * https://leetcode.cn/problems/next-permutation/description/
     * 下一个排列
     */
    @Test
    fun test20() {
        val nums = intArrayOf(1, 2, 3)
        nextPermutation(nums)
        println(nums.contentToString())
    }

    private fun nextPermutation(nums: IntArray) {
        // 从右到左，找到第一个下降的数字，交换到后面最后一个比其大的数字，然后将后面的数字逆序排列
        var index = nums.size - 1
        var down = -1
        while (index > 0) {
            if (nums[index - 1] < nums[index]) {
                down = index - 1
                swapToLastBiggerNumber(nums, down)
                break
            }
            index--
        }
        // 将 down 后面的数字逆序
        nums.sort(down + 1)
    }

    private fun swapToLastBiggerNumber(nums: IntArray, down: Int) {
        var index = nums.size - 1
        while (index > 0) {
            if (nums[down] < nums[index]) {
                // 交换这两个数字
                val temp = nums[index]
                nums[index] = nums[down]
                nums[down] = temp
                break
            }
            index--
        }
    }


    /*
     * https://leetcode.cn/problems/decode-string/description/
     * 字符串解码
     */
    @Test
    fun test21() {
        println(decodeString("3[a]2[bc]"))
        println(decodeString("2[abc]3[cd]ef"))
    }

    private fun decodeString(s: String): String {
        val stack = Stack<Pair<Int, String>>()
        var re = ""
        var num = 0
        s.forEach { c ->
            when (c) {
                '[' -> {
                    stack.push(Pair(num, re))
                    num = 0
                    re = ""
                }

                ']' -> {
                    val (n, r) = stack.pop()
                    re = r + re.repeat(n)
                }

                in '0'..'9' -> {
                    num = num * 10 + c.toString().toInt()
                }

                else -> {
                    re += c.toString()
                }
            }
        }
        return re
    }


    /*
     * https://leetcode.cn/problems/reverse-linked-list/description/
     * 反转链表
     */
    @Test
    fun test22() {
        println(reverseList2(mutableListOf(1, 2, 3, 4, 5)))
        println(reverseList2(mutableListOf(5, 4, 3, 2, 1)))
    }

    private fun reverseList1(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var cur: ListNode? = head

        while (cur != null) {
            // 记录当前节点的下一个节点
            val next: ListNode? = cur.next
            // 然后将当前节点指向 prev
            cur.next = prev

            // prev 和 cur 节点都前进一位
            prev = cur
            cur = next
        }

        return prev
    }

    private fun reverseList2(list: MutableList<Int>): MutableList<Int> {
        val newList = mutableListOf<Int>()
        if (list.isEmpty()) return newList
        var size = list.size
        while (size > 0) {
            size--
            newList.add(list[size])
        }
        return newList
    }

    /*
    * https://leetcode.cn/problems/first-missing-positive/description/
    * 缺失的第一个正数
    */
    @Test
    fun test23() {
        println(firstMissingPositive(mutableListOf(1, 2, 0)))
        println(firstMissingPositive(mutableListOf(3, 4, -1, 1)))
        println(firstMissingPositive(mutableListOf(7, 8, 9, 11, 12)))
    }

    private fun firstMissingPositive(nums: MutableList<Int>): Int {
        for (i in 1..Int.MAX_VALUE) {
            if (!nums.contains(i)) return i
        }
        return 0
    }

    /*
    * https://leetcode.cn/problems/longest-consecutive-sequence/description/
    * 最长连续序列
    */
    @Test
    fun test24() {
        println(longestConsecutive(mutableListOf(0, 3, 7, 2, 5, 8, 4, 6, 0, 1, 99, 98, 97, 96, 95)))
    }

    private fun longestConsecutive(nums: MutableList<Int>): Int {
        if (nums.size <= 1) return nums.size

        nums.sort()

        println(nums)

        // 使用最大堆来保存连续长度的值
        val maxHeap = PriorityQueue<Int> { a, b -> b - a }
        var count = 1
        for (i in 0 until nums.size - 1) {
            // 如果是连续的值，则连续长度直接加1
            if (nums[i + 1] != nums[i]) {
                if (nums[i + 1] - nums[i] == 1) {
                    count++
                } else {
                    // 如果不是连续的值，则连续长度置为1
                    count = 1
                }
            }
            maxHeap.offer(count)
        }
        return maxHeap.peek() ?: 0
    }


    /*
    * https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
    * 搜索旋转排序数组
    */
    @Test
    fun test25() {
        val a = intArrayOf(4, 5, 6, 7, 0, 1, 2)

        println(find(a, 0))
        println(find(a, 1))
    }

    private fun find(nums: IntArray, target: Int): Int {
        var start = 0
        var end = nums.size - 1
        while (start <= end) {
            if (nums[start] == target) {
                return start
            } else {
                start++
            }

            if (nums[end] == target) {
                return end
            } else {
                end--
            }
        }
        return -1
    }


    /*
     * https://leetcode.cn/problems/permutations/description/
     * 全排列
     */
    @Test
    fun test26() {
        println(permute(mutableListOf(1, 2, 3)))
    }

    private fun permute(nums: MutableList<Int>): List<List<Int>> {
        return permute0(nums)
    }

    private fun permute0(nums: MutableList<Int>): MutableList<MutableList<Int>> {
        if (nums.size == 1) return mutableListOf(nums)

        val results = mutableListOf<MutableList<Int>>()

        nums.forEach { num ->

            val filterList = nums.filter { it != num }.toMutableList()
            println(filterList)

            val list = permute0(filterList)

            list.forEach {
                // 把当前位加入列表尾部（头部或者尾部）
                it.add(num)
                results.add(it)
            }
        }
        return results
    }


    /*
     * https://leetcode.cn/problems/house-robber/description/
     * 打家劫舍
     */
    @Test
    fun test27() {
        println(rob(intArrayOf(2, 7, 9, 3, 1)))
        println(rob(intArrayOf(1, 2, 3, 1)))
    }

    private fun rob(nums: IntArray): Int {
        var fpp = nums[0]
        if (nums.size < 2) return fpp

        var fp = Math.max(nums[1], nums[0])

        for (i in 2 until nums.size) {
            val t = Math.max(fp, fpp + nums[i])
            fpp = fp
            fp = t
        }
        return fp
    }

    /*
     * https://leetcode.cn/problems/merge-k-sorted-lists/description/
     * 合并 K 个升序链表
     */
    @Test
    fun test28() {
        val a = mutableListOf(mutableListOf(1, 4, 5), mutableListOf(1, 3, 4), mutableListOf(2, 6))
        val b = mutableListOf<Int>()

        a.forEach { list ->
            list.forEach { b.add(it) }
        }

        b.sort()

        println(b)
    }

    /*
     * https://leetcode.cn/problems/reverse-words-in-a-string/description/
     * 反转字符串中的单词
     */
    @Test
    fun test29() {
        val s = "the sky is blue"
        val list = s.split(" ").toMutableList()
        println(list)
        val newList = mutableListOf<String>()
        var size = list.size - 1
        while (size >= 0) {
            newList.add(list[size])
            size--
        }

        println(newList)

        var str = ""
        newList.forEach { str += "$it " }
        str.substring(0, str.length - 1)

        println(str)
    }

    /*
     * https://leetcode.cn/problems/minimum-path-sum/description/
     * 最小路径和
     */
    @Test
    fun test30() {
        val a = mutableListOf(mutableListOf(1, 3, 1), mutableListOf(1, 5, 1), mutableListOf(4, 2, 1))
        println(minPathSum(a))
    }

    private fun minPathSum(grid: MutableList<MutableList<Int>>): Int {
        val m = grid.size
        val n = grid[0].size
        val dp = IntArray(n)
        dp[0] = grid[0][0]
        for (j in 1 until n) {
            dp[j] = dp[j - 1] + grid[0][j]
        }
        for (r in 1 until m) {
            dp[0] += grid[r][0]
            for (c in 1 until n) {
                dp[c] = Math.min(dp[c], dp[c - 1]) + grid[r][c]
            }
        }
        return dp[n - 1]
    }

    /*
     * https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150
     * 字母异位词分组
     */
    @Test
    fun test31() {
        val a = mutableListOf("eat", "tea", "tan", "ate", "nat", "bat")
        println(groupAnagrams(a))
    }

    private fun groupAnagrams(strs: MutableList<String>): List<List<String>> {
        val group = mutableMapOf<String, MutableList<String>>()
        strs.forEach { w ->
            val k = w.toCharArray().sorted().joinToString("")
            val v = group.getOrDefault(k, mutableListOf())
            v.add(w)
            group[k] = v
        }
        return group.values.toList()
    }

    /**
     * https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
     * 移动零
     */
    @Test
    fun test32() {
        val a = mutableListOf(0, 1, 0, 3, 12)
        println(moveZeroes(a))
        println(moveZeroes2(a))
    }

    private fun moveZeroes(nums: MutableList<Int>): MutableList<Int> {
        var index = 0
        nums.forEach { n ->
            if (n != 0) {
                nums[index] = n
                index++
            }
        }
        while (index < nums.size) {
            nums[index] = 0
            index++
        }

        return nums
    }

    private fun moveZeroes2(nums: MutableList<Int>): MutableList<Int> {
        val noZero = mutableListOf<Int>()
        val zero = mutableListOf<Int>()
        nums.forEach { if (it == 0) zero.add(it) else noZero.add(it) }

        val result = mutableListOf<Int>()
        result.addAll(noZero)
        result.addAll(zero)

        return result
    }

    /*
     * https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150
     * 盛最多水的容器
     */
    @Test
    fun test33() {
        val firstHeights = intArrayOf(1, 8, 6, 2, 5, 4, 8, 3, 7)
        println(maxArea(firstHeights))
    }

    private fun maxArea(heights: IntArray): Int {
        // 将左指针放置在数组的第一个元素
        var left = 0
        // 将右指针放置在数组的最后一个元素
        var right = heights.size - 1
        var result = 0
        // 循环遍历直至左右指针到达同一个位置
        while (left != right) {
            // 宽度的值可以通过右指针的索引减去左指针的索引得到
            val width = right - left
            // 根据题义可知，要想得到最大的盛水面积，高度就需要取左指针和右指针所在元素的最小值
            val height = Integer.min(heights[left], heights[right])
            // 取最大的面积
            result = max(result, width * height)
            if (heights[left] < heights[right]) {
                // 如果左指针对应的元素小于右指针对应的元素，就将左指针向右移动一格
                left++
            } else {
                // 如果左指针对应的元素大于右指针对应的元素，就将右指针向左移动一格
                right--
            }
        }
        return result
    }

}


























